Notes on Starky

Currently it

• Forces constraints to be between two consecutive rows, except first and last, which are handled separately.
• Does not have abstractions allowing for the creation of complex proofs.
• Does not yet implement constant polynomials ('permutation checks'), but a lot of infra is there.
• Implements multiple OODS samples (?)
• Not optimized for very large traces. (no cache-oblivious algorithms FFT)
• No evaluation optimization for constraint polynomials.
• Has active team.
• Implements blinding.

OpenZKP

• Does not use a small field + field extension
• Does not implement constant columns at all.
• Optimizes constraint evaluation.
• Supports constraints over arbitrary distances.
• Supports constraints over arbitrary denominators.
• Unmaintained.
• Aarch64 asm lacking (though x86_64 is there).

Random ideas:

• Interactive proof with one forced Ethereum block after FRI commitment. How many openings are required?

• Build standalone Algebraic DAG library.

• Evaluate over domains larger than the largest coset: Take several random cosets. FRI can no longer reduce to a constant, but can still reduce to poly of degree equal to no cosets, which can be directly evaluated. This allows trace length up to the full size of the Goldilocks coset. (Assuming the extension doesn't affect this somehow).